// 1   2   3   4 
// 5   6   7   8
// 9   10  11  12
// 13  14  15  16
// 1 2 3 4 8 12 16  15 14 13 9 5 6 7 11 10
// 1   2   3   4 
// 5   6   7   8
// 9   10  11  12
// 1 2 3 4 8 12 11 10 9 5 6 7
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<int> ret;
        int row = 0;
        while (2 * row < n && 2 * row < m)
        {
            for (int i = row; i < m - row; ++i)
            {
                ret.push_back(matrix[row][i]);
            }
            for (int i = row + 1; i < n - row; ++i)
            {
                ret.push_back(matrix[i][m - row - 1]);
            }
            for (int i = m - row - 2; i >= row; --i)
            {
                if(2*row + 1!= n)
                    ret.push_back(matrix[n - row - 1][i]);
            }for (int i = n - row - 2; i > row; --i)
            {
                //if (n - row - 1 != i)
                ret.push_back(matrix[i][row]);
            }
            row++;
        }
        return ret;
    }
};
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool b1 = true, b2 = true;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0)
                b1 = false;
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0)
                b2 = false;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0)
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
        }
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0)
                for (int i = 1; i < m; i++) {
                    matrix[i][j] = 0;
                }
        }
        if (b1 == false) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (b2 == false) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
    }
};
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        map<int, int> mm;
        for (auto e : bills) {
            if (e == 5)
                mm[5]++;
            else if (e == 10) {
                if (mm[5] == 0)
                    return false;
                else {
                    mm[5]--;
                    mm[10]++;
                }
            }
            else {
                if (mm[5] >= 1 && mm[10] >= 1) {
                    mm[5]--;
                    mm[10]--;
                }
                else if (mm[5] >= 3) {
                    mm[5] -= 3;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }
}; bool fun(int a, int b) {
    return a > b;
}
class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end(), fun);
        int ret = 0;
        for (int i = 2; i < nums.size(); i++)
        {
            int a = nums[i - 2];
            int b = nums[i - 1];
            int c = nums[i];
            if (b + c > a) {
                ret = a + b + c;
                return ret;
            }
        }
        return ret;
    }
};
int main() {
    vector<vector<int>> vv = { {1,2,3,4},{5,6,7,8},{9,10,11,12} };
    Solution().spiralOrder(vv);
}